package com.yvon.service.demo.algorithm.linkedlist;

/**
 * @author : Yvon
 * @since : 2022-07-13
 */
public class LinkedList {

    public static void main(String[] args) {
        ListNode<Integer> listNode5 = new ListNode<>(5, null);
        ListNode<Integer> listNode4 = new ListNode<>(4, listNode5);
        ListNode<Integer> listNode3 = new ListNode<>(3, listNode4);
        ListNode<Integer> listNode2 = new ListNode<>(2, listNode3);
        ListNode<Integer> listNode1 = new ListNode<>(1, listNode2);
        ListNode<Integer> head = new ListNode<>(0, listNode1);


        printLinkedList(head);
        ListNode<Integer> listNode = reverseLinkedList2(head);
        printLinkedList(listNode);


    }

    public static void printLinkedList(ListNode<Integer> head){
        while(head != null){
            System.out.print(head.value);
            head = head.next;
        }
        System.out.println();
    }

    /**
     * 递归反转链表
     *
     * @param head 头
     * @return ListNode<String>
     * @author : Yvon / 2022-07-13
     */
    public static ListNode<Integer> reverseLinkedList1(ListNode<Integer> head) {
        // Step1：终止条件
        if (head == null || head.next == null) {
            return head;
        }

        // Step2：保存当前节点的下一个结点
        ListNode<Integer> next = head.next;
        // Step3：从当前节点的下一结点开始递归
        ListNode<Integer> pre = reverseLinkedList1(next);
        // Step4：head挂到next节点的后面就完成链表的反转
        next.next = head;
        // 这里的head相当于变成了尾结点，尾结点都是为空，否则会构成环
        head.next = null;
        return pre;
    }

    /**
     * 三指针翻转
     *
     * @param head 头
     * @return ListNode<Integer>
     * @author : Yvon / 2022-07-13
     */
    public static ListNode<Integer> reverseLinkedList2(ListNode<Integer> head) {
        // 单链表为空或只有一个节点，直接返回原单链表
        if (head == null || head.next == null) {
            return head;
        }

        // 前一结点指针
        ListNode<Integer> preNode = null;
        // 当前结点指针
        ListNode<Integer> curNode = head;
        // 下一结点指针
        ListNode<Integer> nextNode;
        while (curNode != null) {
            // nextNode 指向下一结点
            nextNode = curNode.next;
            // 将当前结点的next指针指向前一个节点
            curNode.next = preNode;
            // preNode 指针向后移动
            preNode = curNode;
            // curNode指针向后移动
            curNode = nextNode;
        }
        return preNode;
    }

}
